#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 5e4 + 5;

int n, m;
int mo[N], sum[N];
int np[N], primes[N], tot;
void init(int n) {
  np[1] = 1;
  mo[1] = 1;
  rep(i, 2, n) {
    if (!np[i]) {
      primes[++tot] = i;
      mo[i] = -1;
    }
    rep(j, 1, tot) {
      ll k = 1ll * primes[j] * i;
      if (k > n) break;
      np[k] = 1;
      if (i % primes[j] == 0) {
        mo[k] = 0;
        break;
      } else {
        mo[k] = -mo[i];
      }
    }
  }
  rep(i, 1, n) sum[i] = sum[i - 1] + mo[i];
}
ll f(ll a, ll b) {
  if (a > b) swap(a, b);
  ll ans = 0;
  for (ll l = 1, r = 1; l <= a; l = r + 1) {
    ll x = a / l, y = b / l;
    r = min({a, a / x, b / y});
    ans += 1ll * (sum[r] - sum[l - 1]) * x * y;
  }
  return ans;
}
void solve() {
  int a, b, d;
  cin >> a >> b >> d;
  a /= d, b /= d;
  cout << f(a, b) << endl;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  init(5e4);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}